package double_pointer;
import java.util.*;

public class threeSum {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ret = new ArrayList<>();
        for(int i = 0;i < nums.length-2;i++) {
            int left = i+1;
            int right = nums.length-1;
            while(left < right) {
                int sum = nums[left] + nums[right];

                if(sum > -nums[i]) {
                    right--;
                }else if(sum < -nums[i]) {
                    left++;
                }else {
                    List<Integer> arr = new ArrayList<>();
                    arr.add(nums[left]);
                    arr.add(nums[i]);
                    arr.add(nums[right]);
                    while(left < right &&nums[left+1] == nums[left]) {
                        left++;
                    }
                    while(left < right &&nums[right-1]== nums[right]) {
                        right--;
                    }
                    left++;
                    right--;
                    ret.add(arr);
                }
            }
            while(i < nums.length-1 && nums[i+1] == nums[i]) {
                i++;
            }

        }
        return ret;

    }
}
